package leetcode;

/**
 * 122. 买卖股票的最佳时机 II    https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
 */
public class LeetCode122 {

    // 1、暴力dfs
    public static int maxProfit1(int[] prices) {
        return dfs(0, prices.length - 1, prices, false, 0);
    }

    public static int dfs(int index, int level, int[] prices, boolean buy, int ans) {
        if (index == level) {
            if (buy) {
                ans += prices[index];
            }
            return ans;
        }

        if (!buy) {
            int buyAns = dfs(index + 1, level, prices, true, ans - prices[index]);
            int noBuyAns = dfs(index + 1, level, prices, false, ans);
            return Math.max(buyAns, noBuyAns);
        } else {
            int selfAns = dfs(index + 1, level, prices, false, ans + prices[index]);
            int noSelfAns = dfs(index + 1, level, prices, true, ans);
            return Math.max(selfAns, noSelfAns);
        }
    }

    // 2、动态规划
    public static int maxProfit2(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] -= prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }

    // 3、贪心算法（涨了就买）
    public static int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int ans = 0;
        int diff;
        for (int i = 1; i < prices.length; i++) {
            diff = prices[i] - prices[i - 1];
            if(diff > 0) {
                ans += diff;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};       // 7
        System.out.println(maxProfit(prices));
        int[] prices1 = {1, 2, 3, 4, 5};       // 4
        System.out.println(maxProfit(prices1));
        int[] prices2 = {7, 6, 4, 3, 1};       // 0
        System.out.println(maxProfit(prices2));
    }
}
